/* ************************************************************************
> File Name:     longest-common-subsequence.cpp
> Author:        程序员lyl
> 微信公众号:    雨特宙
> Created Time:  2024年03月23日 星期六 10时37分15秒
> Description:   
 ************************************************************************/
#include<iostream>
#include<string>
#include<vector>
using namespace std;


int longestCommonSubsequence(string text1, string text2){
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for(int i = 1; i <= text1.size(); i++){
        for(int j = 1; j <= text2.size(); j++){

            if(text1[i-1] == text2[j-1]){

                dp[i][j] = dp[i-1][j-1] +1;
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

    }
    return dp[text1.size()][text2.size()];

}

int main(){
    string str1, str2;
    cout <<"str1:";
    cin >> str1;
    cout<<"str2:";
    cin >> str2;
    int res = longestCommonSubsequence(str1, str2);
    cout<<"res:"<<res;

}


